package problems.practice;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * 187. 重复的DNA序列
 * https://leetcode.cn/problems/repeated-dna-sequences
 *
 * @author habitplus
 * @since 2022/8/9 21:35
 */
public class T187 {

    static final int L;
    static final HashMap<Character, Integer> BIN_MAP = new HashMap<>();

    static {
        L = 10;
        BIN_MAP.put('A', 0);
        BIN_MAP.put('C', 1);
        BIN_MAP.put('G', 2);
        BIN_MAP.put('T', 3);
    }


    public List<String> findRepeatedDnaSequences(String s) {
        List<String> ans = new ArrayList<>();
        if (s == null || s.length() <= L) {
            return ans;
        }

        HashMap<Integer, Integer> cnt = new HashMap<>();
        int n = s.length();
        int x = 0;

        for (int i = 0; i < L - 1; ++i)
            x = (x << 2) | BIN_MAP.get(s.charAt(i));


        for (int i = 0; i <= n - L; ++i) {
            x = ((x << 2) | BIN_MAP.get(s.charAt(i + L - 1))) & ((1 << (L * 2)) - 1);
            cnt.put(x, cnt.getOrDefault(x, 0) + 1);
            if (cnt.get(x) == 2) {
                ans.add(s.substring(i, i + L));
            }
        }
        return ans;
    }

    public List<String> findRepeatedDnaSequences1(String s) {
        List<String> ret = new ArrayList<>();
        if (s == null || s.length() <= 10) return ret;

        HashMap<String, Integer> map = new HashMap<>();
        StringBuffer buffer = new StringBuffer();
        char[] chs = s.toCharArray();
        int n = chs.length;
        String tmp;
        int cnt;
        for (int i = 0; i < n; ++i) {
            buffer.append(chs[i]);
            if (i >= 9) {
                tmp = buffer.toString();
                cnt = map.getOrDefault(tmp, 0) + 1;
                if (cnt == 2) ret.add(tmp);
                map.put(tmp, cnt);
                buffer.deleteCharAt(0);
            }
        }

        return ret;
    }
}
